#ifndef _GTREE_H_
#define _GTREE_H_

#include "Tree.h"
#include "GTreeNode.h"
#include "Exception.h"
#include "LinkQueue.h"

namespace MySTL
{

template < typename T >
class GTree : public Tree<T>
{
public:
	bool insert(const T& value, TreeNode<T>* parent);
	bool insert(TreeNode<T>* node);
	bool remove(TreeNode<T>* node, bool need_to_delete = true);
	GTreeNode<T>* find(const T& value) const;
	GTreeNode<T>* find(TreeNode<T>* node) const;
	GTreeNode<T>* root() const;
	int degree() const;
	int height() const;
	int count() const;
	void clear();

	bool begin();
	bool end();
	bool next();
	GTreeNode<T>* current();

	~GTree();

public:
	static void clear(GTreeNode<T>* root);

protected:
	GTreeNode<T>* find(GTreeNode<T>* root, const T& value) const;
	GTreeNode<T>* find(GTreeNode<T>* root, GTreeNode<T>* node) const;
	int degree(GTreeNode<T>* root) const;
	int height(GTreeNode<T>* root) const;
	int count(GTreeNode<T>* root) const;
protected:
	LinkQueue<GTreeNode<T>*> m_foreach_queue;
};

template < typename T >
bool GTree<T>::insert(const T& value, TreeNode<T>* parent)
{
	bool ret = true;

	GTreeNode<T>* node = GTreeNode<T>::NewNode();
	if (NULL != node)
	{
		node->parent = parent;
		node->value = value;

		ret = insert(node);

		if (false == ret)
		{
			delete node;
		}
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create GTreeNode in bool GTree<T>::insert(const T& value, TreeNode<T>* parent)");
	}

	return ret;
}

template < typename T >
bool GTree<T>::insert(TreeNode<T>* node)
{
	GTreeNode<T>* gNode = dynamic_cast<GTreeNode<T>*>(node);
	bool ret = (NULL != gNode);

	if (ret)
	{
		if (NULL == root())
		{
			gNode->parent = NULL;
			this->m_root = gNode;
		}
		else
		{
			GTreeNode<T>* parent = find(gNode->parent);
			if (NULL != parent && parent->child.find(gNode) < 0)
			{
				parent->child.insert(gNode);
			}
			else
			{
				ret = false;
			}
		}
	}

	return ret;
}

template < typename T >
bool GTree<T>::remove(TreeNode<T>* node, bool need_to_delete)
{
	GTreeNode<T>* gNode = find(node);
	bool ret = (NULL != gNode);

	if (ret)
	{
		GTreeNode<T>* parent = dynamic_cast<GTreeNode<T>*>(gNode->parent);
		if (NULL != parent)
		{
			parent->child.remove(parent->child.find(gNode));
		}
		gNode->parent = NULL;
		if (root() == gNode)
		{
			this->m_root = NULL;
		}
		if (need_to_delete)
		{
			clear(gNode);
		}

		m_foreach_queue.clear();
	}

	return ret;
}

template < typename T >
GTreeNode<T>* GTree<T>::find(const T& value) const
{
	return find(root(), value);
}

template < typename T >
GTreeNode<T>* GTree<T>::find(TreeNode<T>* node) const
{
	return find(root(), dynamic_cast<GTreeNode<T>*>(node));
}

template < typename T >
GTreeNode<T>* GTree<T>::root() const
{
	return dynamic_cast<GTreeNode<T>*>(this->m_root);
}

template < typename T >
int GTree<T>::degree() const
{
	return degree(root());
}

template < typename T >
int GTree<T>::height() const
{
	return height(root());
}

template < typename T >
int GTree<T>::count() const
{
	return count(root());
}

template < typename T >
void GTree<T>::clear()
{
	clear(root());
	this->m_root = NULL;
	m_foreach_queue.clear();
}

template < typename T >
bool GTree<T>::begin()
{
	bool ret = (NULL != root());

	if (ret)
	{
		m_foreach_queue.clear();
		m_foreach_queue.enqueue(root());
	}
	
	return ret;
}

template < typename T >
bool GTree<T>::end()
{
	return m_foreach_queue.length() <= 0;
}

template < typename T >
bool GTree<T>::next()
{
	bool ret = !end();

	if (ret)
	{
		GTreeNode<T>* node = m_foreach_queue.dequeue();
		if (NULL != node)
		{
			for (node->child.move(0); !node->child.end(); node->child.next())
			{
				m_foreach_queue.enqueue(node->child.current());
			}
		}
	}

	return ret;
}

template < typename T >
GTreeNode<T>* GTree<T>::current()
{
	if (!end())
	{
		return m_foreach_queue.top();
	}
	else
	{
		THROW_EXCEPTION(InvalidOperationException, "Invalid operation in GTreeNode<T>* GTree<T>::current()");
	}
}

template < typename T >
GTree<T>::~GTree()
{
	clear();
}

template < typename T >
void GTree<T>::clear(GTreeNode<T>* root)
{
	if (NULL != root)
	{
		for (root->child.move(0); !root->child.end(); )
		{
			clear(root->child.current());
		}

		GTreeNode<T>* parent = dynamic_cast<GTreeNode<T>*>(root->parent);
		if (NULL != parent)
		{
			parent->child.remove(parent->child.find(root));
		}

		if (root->need_to_delete())
		{
			delete root;
		}
	}
}

template < typename T >
GTreeNode<T>* GTree<T>::find(GTreeNode<T>* root, const T& value) const
{
	GTreeNode<T>* ret = NULL;

	if (NULL != root)
	{
		if (root->value == value)
		{
			ret = root;
		}
		else
		{
			for (root->child.move(0); !root->child.end() && !ret; root->child.next())
			{
				ret = find(root->child.current(), value);
			}
		}
	}

	return ret;
}

template < typename T >
GTreeNode<T>* GTree<T>::find(GTreeNode<T>* root, GTreeNode<T>* node) const
{
	GTreeNode<T>* ret = NULL;

	if (NULL != root)
	{
		if (root == node)
		{
			ret = root;
		}
		else
		{
			for (root->child.move(0); !root->child.end() && !ret; root->child.next())
			{
				ret = find(root->child.current(), node);
			}
		}
	}

	return ret;
}

template < typename T >
int GTree<T>::degree(GTreeNode<T>* root) const
{
	int ret = 0;

	if (root)
	{
		ret = root->child.length();

		for (root->child.move(0); !root->child.end(); root->child.next())
		{
			int d = degree(root->child.current());
			if (d > ret)
			{
				ret = d;
			}
		}
	}

	return ret;
}

template < typename T >
int GTree<T>::height(GTreeNode<T>* root) const
{
	int ret = 0;

	if (root)
	{
		for (root->child.move(0); !root->child.end(); root->child.next())
		{
			int h = height(root->child.current());
			if (h > ret)
			{
				ret = h;
			}
		}

		ret = ret + 1;
	}

	return ret;
}

template < typename T >
int GTree<T>::count(GTreeNode<T>* root) const
{
	int ret = 0;

	if (root)
	{
		ret = 1;

		for (root->child.move(0); !root->child.end(); root->child.next())
		{
			ret += count(root->child.current());
		}
	}

	return ret;
}

}

#endif